Add Book to My BookshelfPurchase This Book Online

Chapter 4 - Routing Protocols Used in TCP/IP

Cisco TCP/IP Routing Professional Reference
Chris Lewis
  Copyright © 1999 The McGraw-Hill Companies, Inc.

Routing Protocols: Link State
Distance vector and link state are just two different ways of automatically updating routing tables in routers. A link state protocol has totally different mechanisms for gathering route information and calculating which route will be put into the routing table. The fact is, both distance vector and link state protocols should choose the same next-hop router to put in the routing table for most destinations.
We can introduce the concepts of link state routing as follows:
  1. A router will find out which routers are directly connected to it.
  2. Each router will send out link state advertisements (LSAs), which list the names and cost to each of its neighbors.
  3. The LSA sent to a given router's neighbors will be forwarded to every other router.
  4. Each router now knows the complete topology of the internetwork and computes optimal routes for every destination for entry into the routing table.
Before we consider implementations of the link state type routing protocol, it is worth finding the answers to two questions: How do we ensure that a router interprets link state packets in the correct order? And how are actual routes computed once the LSAs have been received?
A timestamp could be put on each LSA, but that would require very accurate synchronization of every router on the internetwork. What is implemented now is a combination of sequence number and age. Each router will start sending LSAs with sequence number 0 and increment this value each time an LSA is sent. In addition, any given LSA may not exist in the system longer than a predetermined time, normally an hour.
Once a router has a complete LSA database (referred to by Cisco as a Topological database), it may compute routes for entry into the routing table. This is done using Dijkstra's algorithm. Because you cannot alter anything within Dijkstra's algorithm when configuring a router, I will not go in to its logic. In concept, it is a kind of trial-and-error mechanism in that it tries different routes to get to the same destination, calculates the metric for each, and then selects the route with the lowest metric. Clearly, the larger the internetwork, the more possible permutations the algorithm must try out before finding the optimal route. This can place a heavy burden on a router's processor when a link state protocol is used in a large internetwork. This burden can, however, be reduced through proper design.
OSPF: Open Shortest Path First
OSPF was designed by the Internet Engineering Task Force in the late 1980s because it was clear that RIP was increasingly unable to serve large heterogeneous networks, particularly the Internet. OSPF is an open standard, implemented by all major router manufacturers. OSPF is a classic link state routing protocol and requires that the network be physically configured in a routing hierarchy; this means that a central backbone connects different routing areas together. OSPF received its name as it is an open standard and uses the Shortest Path First algorithm (otherwise known as the Dijkstra algorithm).
It should be noted that OSPF only supports routing for IP. OSPF was designed as an Interior Gateway Protocol, but it is capable of receiving routes from and sending routes to different autonomous systems.
An OSPF internetwork normally is divided into a number of areas that contain hosts and routers. These areas should be designed so that cross-area communication is kept to a minimum. Within the autonomous system, some routers with multiple interfaces can be configured as border area routers, which means one interface will be in one area, a second interface in another. In this case, the router keeps a topological database for each area that it is in.The only way to get from one area to another area is via the backbone, which is always configured as area 0. It must be noted that the backbone can be noncontiguous to make routing more efficient. In this case, backbone connectivity is restored by virtual links that are configured between any backbone routers that share a link to a nonbackbone area and function as if they were direct links.
In OSPF, link state advertisements are sent to all other routers within a given area. This contrasts with a distance vector protocol (such as RIP or IGRP) that sends all of the routing tables in updates messages, but only to their neighbors. LSAs include data such as metrics used, interface address, and other variables. A topological database is present in each router and contains the collection of LSA information, giving an overall picture of networks in relation to routers. Note that all routers within a given area have identical topological databases.
As previously mentioned, an OSPF backbone area is used to connect all other areas together and is responsible for transferring routing information among areas. As might be expected, there are two types of routing within OSPF, one for within a given area (intra-area routing), and the other for between areas (inter-area routing). Figure 4-13 shows a simple OSPF hierarchical internetwork.
Figure 4-13: An OSPF hierarchial internetwork
In order for the host 1 in area 1 to transmit data to host 2 in area 2, the packets must be sent to router 2, which connects area 1 to the backbone, which then forwards the packet to router 5, which connects area 2 to the backbone, which finally gives the packet to its ultimate destination, host 2. The backbone area is labeled area 0 and, as far as the routing algorithms go, acts much like any other area.
It should be noted that the internal topology of any area is invisible to every other area. This means that each router within a given area will know how to get to every other router within its area, and how to get to the backbone. It will not know how many routers exist or how they are connected for any other area. This is important to keep in mind when designing dial backup systems for OSPF-based internetworks. (This issue will be revisited in Chap. 7.)
As you can see, an internetwork based around a true link state protocol such as OSPF is considerably more complex to design and operate than one based on a distance vector protocol. As with all things in life, there are tradeoffs. With a distance vector routing protocol, the internetwork can be designed, deployed, and troubleshot fairly easily; within larger networks, however, problems occur with the size of routing table updates and speed of convergence. With link state routing, an internetwork is more complex to design and troubleshoot, and uses more router processor time, but it does converge quickly.
This covers protocol initialization for routers connected on point-to-point circuits. On LANs, things are a little different. On a LAN, several routers may be connected, in which case one will be elected as the designated router and another as its backup. The designated router is responsible primarily for generating LSAs for the LAN to all other networks in the OSPF area. (Note that OSPF areas can be termed domains.)
The concept of adjacencies also is important in the world of OSPF. Two routers are said to be adjacent when they have synchronized their link state databases, that is to say, they have the same map of the routing area to which they belong. It is important that pairs of routers become adjacent, because routing information protocol packets will only be transferred between routers that have become adjacent.
Another key feature of OSPF is route aggregation, which minimizes entries in the routing table and topological database in the receiving routers and keeps protocol traffic to a minimum (Fig. 4-14). The routing table for router B shows entries learned about via OSPF for two adjacent subnets, 200.1.1.8 and 200.1.1.12, that both exist in area 1. Because router B is an area border router, it can aggregate these two subnets, using a different subnet mask, so that router C needs only one entry in its routing table to reach both subnets.
Figure 4-14: An example of OSPF route aggregation
Configuring OSPF.     In OSPF, there are three types of routers:
  A backbone router has its interface connected only to the backbone.
  An area border router attaches to multiple areas.
  An internal router has all directly connected interfaces within the same area.
The following is a typical configuration to define an OSPF internal or backbone router process on a Cisco router:
router ospf 50
network140.8.0.0  0.0.255.255  area 0
The first line defines OSPF as a routing process with process ID 50; this is an internally used identification number for each instance of the OSPF routing process run on a router. The second line identifies all interfaces that will participate in the OSPF routing process. In this case, all interfaces belonging to the 140.8.0.0 network participate. The wildcard mask (in this case 0.0.255.255) can be thought of as an inverse subnet mask, meaning that, in this instance, it masks out any bits in the third and fourth octet when determining if an interface will run OSPF. The second line also identifies the area to which the router belongs (in this case area 0, the backbone).
The following is a typical configuration to define an OSPF inter-area router process on a Cisco router:
router ospf 62
network 180.8.2.0  0.0.0.255 area 0
network 180.8.0.0  0.0.255.255 area 2
In this instance, all interfaces with 180.8.2 as the first 3 octets are considered part of area 0. All interfaces that have 180.8 as the first 2 octets of their addresses are considered to be part of area 2.
Let's use the lab we built in Chap. 3 to explore OSPF configuration, as shown in Fig. 4-15.
Figure 4-15: Basic configuration for an OSPF internetwork
To configure the routers for this network configuration to be serviced by OSPF, delete any router IGRP, or IP default-network commands left in the router configurations. Next insert the following commands: In router 1:
Router1(config)#router ospf 10
Router1 (config-router)network 120.0.0.0 0.255.255.255 area 0
In router 2:
Router2(config)#router ospf 10
Router2(config-router)#network 120.0.0.0 0.255.255.255 area 0
Router2(config-router)#network 150.1.0.0 0.0.255.255 area 1
In router 3:
Router3(config)#router ospf 10
Router3(config-router)#network 150.1.0.0 0.0.255.255 area 1
In this configuration, OSPF will produce the same results as IGRP in terms of route selection for entry into the routing table. Let's look at the routing tables of each router, as shown in Fig. 4-16.
Router 3
router3#sho ip route
Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP
D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP
i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default
Gateway of last resort is not set
O IA 120.0.0.0 [110/74] via 150.1.1.1, 04:45:33, Serial0
C  150.1.0.0 is directly connected, Serial0
Router 2
router2>sho ip route
Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP
D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP
i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default
Gateway of last resort is not set
C 120.0.0.0 is directly connected, Ethernet0
C 150.1.0.0 is directly connected, Serial0
Router 1
routerl >sho ip rout
Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP
D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP
i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate defauft
Gateway of last resort is not set
C  120.0.0.0 is directly connected, Ethernet0
O IA 150.1.0.0 [110/74] via 120.1.1.2, 04:49:28, Ethernet0
Figure 4-16: Routing tables generated by OSPF
These routing tables show that routers 1 and 3 learned of networks via an OSPF inter-area routing process. The administrative distance for OSPF is shown, along with the metric for the route (110/74). As usual, the routing table shows the next-hop IP address and the interface to use to get to this next hop.The interesting thing is that the time specified for when the route was last updated is 4 hours, 49 minutes, 28 seconds. This is how long the routers have been up. Essentially there have been no updates to the routes because nothing on the internetwork has caused the routes to be recalculated. With OSPF, each router knows that every other router is there and available through the use of hello packets. In a distance vector protocol, updates to routes typically occur every minute, and if this timer increases to more than 3 minutes or so, it is assumed that the route is no longer valid.
There are three other useful commands for OSPF systems, which we will examine in turn. These are:
  show ip ospf neighbor
  show ip ospf interface
  show ip ospf database
Entering the following command will produce the display shown:
Router1>sho ip ospf neighbor
Neighbor IDPriStateDead TimeAddressInterface
150.1.1.11FULL/DR0:00:32120.1.1.2Ethernet0
This display shows the neighbor IP address, its OSPF priority and state, the time the router will wait for another hello packet before this neighbor will be declared dead, and the address and interface through which this neighbor is reachable.
routerl > sho ip ospf interface
Ethernet0 is up, line protocol is up
Internet Address 120.1.1.1 255.0.0.0, Area 0
Process ID 10, Router ID 120.1.1.1, Network Type BROADCAST, Cost: 10
Transmit Delay is 1 sec, State BDR, Priority 1
Designated Router (ID) 150.1.1.1, Interface address 120.1.1.2
Backup Designated router (ID) 120.1.1.1, Interface address 120.1.1.1
Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5
Hello due in 0:00:08
Neighbor Count is 1, Adjacent neighbor count is 1
Adjacent wdh neighbor 150.1.1.1 (Designated Router)
Serial0 is administratively down, line protocol is down
OSPF not enabled on this interface
Serial1 is administratively down, line protocol is down
OSPF not enabled on this interface
Figure 4-17: The show ip ospf interface command
The command shown in Fig. 4-17 gives more information on the specific OSPF setup on each interface, such as:
  The interface address, netmask, and area ID.
  The OSPF process ID (synonymous with the autonomous system number), ID used by the router (in this case its IP address), network type, and link cost.
  The timers used in the hello neighbor discovery process.
  Acount of the number of neighbors and a list of the routers that have achieved an adjacent condition. (Adjacency is achieved if two routers have the same topology table.)
The final command to look at for this configuration is the show ip ospf database command, which shows us the table of link state advertisements the router uses as input to the Dijkstra algorithm to determine the routing table (Fig. 4-18).
router1> show  ip  ospf  database
OSPF Router with ID (120.1.1.1) (Process ID 10)
Router Link States (Area 0)
ADV RouterAgeSeq#ChecksumLink count
120.1.1.1620x8000000E0x8AC31
150.1.1.1     58 0x8000000F 0x30C1
Net Link States (Area 0)
ADV RouterAgeSeq#Checksum
150.1.1.1580x8000000D0x4DD5
Summary Net Link States (Area 0)
ADV RouterAge  Seq#Checksum
150.1.1.1580x8000000D0xC31C
Figure 4-18: The show ip ospf database command
This supplies fairly straightforward information. The Link ID is the router's IP address for which information is being given. The ADV Router is the router that advertised the Link ID previously listed. (In this case, router 150.1.1.1 advertises the 150.1.0.0 network, the 120.1.1.2 interface, and the 150.1.1.1 interface.) The sequence number is used to detect old, duplicate, or out-of-sequence link state advertisements. The link count identifies the number of interfaces running OSPF in the router.
Now that we have seen what the topology database looks like during normal operation, let's try the following. If we connect the Ethernet interface on router 3 to the hub for the configuration shown in Fig. 4-15, an interesting situation arises. This is the configuration used to test the IP default-network command earlier in this chapter. In that situation, connecting the Ethernet 0 interface on router 3 to the hub did not adversely affect the operation of IGRP.
In OSPF, things are a little different due to the use of LSAs.
To perform this experiment, add an entry to the ospf 10 section on router 3 for the 193.1.1.0 network to area 0, as follows:
Router3(config)#router ospf 10
Router3(config-router)#network 193.1.1.0 0.0.0.255 area 0
Now try to ping 120.1.1.1 from router 3.
Router3#ping 120.1.1.1
Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 120.1.1.1, timeout is 2 seconds:
……
Success rate is 0 percent (0/5)
This happens because the routing table has changed, so let's look at the routing table of router 3 and see what happened.
Router3#sho ip route
Gateway of last resort is not set
C150.1.0.0 is directly connected, Serial0
C193.1.1.0 is directly connected, Ethernet0
The reason for this is that the topology database is now supplying information to the Dijkstra algorithm, which prevents the 120.0.0.0 network from being entered in the routing table. The topology database knows about the 120.0.0.0 network, but it does not make it into the routing table, so router 3 no longer can send packets there. This topology database is now shown as follows:
Router3#sho ip ospf database
Router Link States (Area 1)
Link IDADV RouterAgeSeq#ChecksumLink count
150.1.1.1150.1.1.1770x800000100x2E5D2
193.1.1.1193.1.1.1960x800000120x54092
Summary Net Link States (Area 1)
Link IDADV RouterAgeSeq#Checksum
120.0.0.0150.1.1.1760x8000000E0x37FC
193.1.1.0193.1.1.13950x800000010xFCCD
Router Link States (Area 0)
Link IDADV RouterAgeSeq#ChecksumLink count
193.1.1.1193.1.1.13900x800000030xFEF91
Summary Net Link States (Area 0)
Link IDADV RouterAgeSeq#Checksum
150.1.0.0193.1.1.13950x800000010x5769
Clearly, the OSPF link state advertisement mechanism and Dijkstra algorithm are less forgiving than the distance vector system.
Optional OSPF Configuration Commands.     The preceding configurations covered what was necessary to get OSPF up and running with default values. The following commands are optional if you want to customize your environment. This should be done with caution, because many of the commands need all interfaces on the internetwork to have the same values applied for correct routing.
  ip ospf retransmit-interval
  ip ospf priority number
  ip ospf hello-interval
  ip ospf dead-interval
  area n stub
  area n range aa.aa.aa.aa mm.mm.mm.mm
  no ospf auto-cost-determination
The ip ospf retransmit-interval command specifies the number of seconds between link state advertisement retransmissions for adjacencies on an OSPF interface.
The ip ospf priority number command sets the priority of a given router, which is used during router initialization to determine the designated and backup router for a LAN.
The ip ospf hello-interval command is used to define the interval in seconds between hello packets sent out by a router.
The command ip ospf dead-interval defines the length of time a router waits to hear hello packets from another OSPF router before declaring it down.
In the command area n stub, the n here is the area number. A stub area is one into which no route information regarding other area numbers is sent. Instead, the stub area border router generates a default route for any router in the stub area to use if a packet needs to be sent to another area number. This reduces the amount of LSA packets in a routing area.
The area n range aa.aa.aa.aa mm.mm.mm.mm command is used by area border routers to reduce the number of subnets advertised between areas. This is the command used to implement the route summarization shown in Fig. 4-14. In this figure, an area border router summarizes two adjacent subnets into one subnet for advertisement to another router. In this example, the command would be:
area 2 range 200.1.1.8 255.255.255.248
To explain the no ospf auto-cost-determination command, it must be noted that prior to release 10.3 on Cisco IOS, OSPF assigned a default cost to each serial link, much the same way IGRP operated in the lab of Chap. 3. With IGRP, we had to assign bandwidth commands for each interface, so that the route calculation used appropriate metrics. The same was true in OSPF, where specific ip ospf cost entries had to be put in for each interface to associate the correct cost for the bandwidth available. Cisco's OSPF implementation now assigns cost values based on the bandwidth of the link in use. For example, a 64 kbps link gets a cost (metric) of 1562, whereas a T-1 gets a cost of 64. The no ospf auto-cost-determination command disables this feature and allows a network administrator to customize the cost of links used in the internetwork.
Variable-Length Subnet Masks in OSPF.     Previously we mentioned that VLSM can save address space on an internetwork. An example of VLSM is given in Fig. 4-19. In this figure, OSPF will distribute information regarding the two netmasks identified throughout the internetwork. This is useful, because we might need to assign a netmask of 255.255.255.0 to the 160.4.3.0 subnet to accommodate all the hosts on this subnet. If we only need a 255.255.255.224 netmask for the number of hosts on the 160.4.4.32 subnet, however, we can assign this netmask and use addresses in the range 160.4.4.65 to 160.4.4.254 elsewhere in the internetwork.
Figure 4-19: Variable-length subnet masks in OSPF
OSPF will keep track of all these subnets and treat them as if they were separate network numbers. This type of network configuration would not be possible with IGRP, because IGRP would summarize the major network number 160.4.0.0 on both entry points to the 150.1.0.0 network, potentially leading to packets destined for the 160.4.3.0 subnet (this is using a netmask of 255.255.255.0) being delivered to the 160.4.4.0 subnet.
The ability to use different values for the subnet mask and have discontinuous subnets is useful for an internetwork like the Internet; on a private internetwork, however, they can easily cause severe problems that are difficult to resolve. Let's explore what could happen to the configuration of the routers in Fig. 4-20 that would cause severe problems.
Figure 4-20: Correct use of VLSM to support discontinuous subnets
This numbering scheme means that for subnet A, we can assign host addresses from 160.4.8.49 to 160.4.8.62. For subnet B, we can assign host addresses within the range 160.4.8.65 to 160.4.8.126. This is a correct configuration, but it is easy to make mistakes and get into serious trouble, even on a very simple internetwork such as this. Suppose the administrator for router 1 realizes he is running out of addresses for subnet A hosts, and, knowing that OSPF supports VLSM, decides to change the mask used on subnet A to 255.255.255.192. The effect of this causes an interesting problem.
With a 255.255.255.192 mask, the first subnet, from 160.4.8.0 to 160.4.8.63 should not be used, because as with all subnet and host values, the first and last in a subnet are not usable. This means that all the hosts numbered from 49 to 62 are no longer valid in subnet A.
Suppose this error is recognized and the administrator decides to reinstate the original subnet A values and generate another subnet off a different interface on router 1. This time the administrator chooses subnet 160.4.8.96 with a mask of 255.255.255.224, giving addressable hosts in the range 160.4.8.97 to 160.4.8.126. This will cause a problem with subnet B, because this range of addresses is legal for subnet B and the new subnet. With this new configuration, routers 1 and 2 will not know where to send packets destined for these hosts. Unless you really need it, VLSM can cause problems on complex internetworks.
Integrated IS-IS
The IS-IS protocol has its origins in OSI. IS-IS stands for Intermediate System to Intermediate System, which means it is used by routers to talk to each other; in OSI terms, an Intermediate System is OSI-speak for a router. IS-IS is a link state protocol and is utilized in Digital Equipment Corporation's DECnet Phase V. To give the protocol a wider appeal, it was made "integrated" so that it would carry route information for protocols other than OSI, most notably the TCP/IP protocols.
The technology behind the protocol is similar to OSPF; it uses LSAs sent to all routers within a given area and hello packets to detect whether a router is still functioning.
Nothing more will be said of Integrated IS-IS, because I recommend that if you want to use a link state protocol, you use OSPF.

 


 
Books24x7.com, Inc © 2000 –  Feedback